from collections import defaultdict
from typing import List


class Solution:
    """
    由于收费是按顺序收费的，所以每次找零钱跟后面的没有关系，故只需要每次收费时手里的钱都能满足这一次找零即可，符合贪心算法使用场景。
    本题贪心的要点：收到20块钱时，找钱要尽可能先使用10块找零，即尽可能多的留下5块钱，不然收到10块时找不开。
    思路：找钱时只有5块和10块两种，所以使用一个hash表记录5块和10块的个数，遍历整个bills列表，当需要5块钱但5块钱的个数为0时，返回False，遍历
         结束返回True
    """
    @staticmethod
    def lemonade_change(bills: List[int]):
        # 使用defaultdict定义一个各个key的初始value为0的字典，便于计算
        diff_num = defaultdict(int)
        for bill in bills:
            # 每次先收钱，数量+1
            diff_num[bill] += 1
            # 收完钱计算该找的零钱
            diff = bill - 5
            # 循环计算找零，直到diff=0即找完为止
            while diff:
                # 收到20块钱且手里有10块钱时，先用10块找零
                if diff >= 10 and diff_num[10]:
                    # 更新剩余需要找零的钱数
                    diff -= 10
                    # 手里10块的个数-1
                    diff_num[10] -= 1
                # 10块不够再使用5块
                elif diff >= 5 and diff_num[5]:
                    diff -= 5
                    diff_num[5] -= 1
                # 零钱不够找
                else:
                    return False
        return True
